#pragma once

#include <iostream>
#include <vector>
using namespace std;

namespace CloseHash
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行
		}
	};

	template<>
	struct HashFunc<string> // 上面的特化
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (const auto& ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			//if (_table.size() == 0 || 10 * _size / _table.size() >= 7) // 负载因子到了就扩容
			//{
			//	size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
			//	vector<HashData<K, V>> newTables; //创建一个vector，很麻烦，所以用下面的方法(复用了)
			//	newTables.resize(newSize);
			//	
			//	for () // 旧表的数据映射到新表
			//	{
			//	}
			//}

			if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 负载因子到了就扩容
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize);

				for (const auto& e : _tables) // 旧表的数据映射到新表
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}

				_tables.swap(newHT._tables);
			}

			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size(); // 如果是负数会整形提升成无符号再取模，没问题

			while (_tables[hashi]._state == EXIST) // 线性探测
			{
				hashi++;
				hashi %= _tables.size();
			}

			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_size;

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			if (_size == 0)
			{
				return nullptr;
			}

			Hash hs;
			size_t start = hs(key) % _tables.size();
			size_t hashi = start;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];
				}

				hashi++;
				hashi %= _tables.size();

				if (start == hashi) // 防止极端情况：状态全是删除，当hashi回到初始时就跳出
				{
					break;
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_size;
				return true;
			}
			else
			{
				return false;
			}
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._state == EXIST)
				{
					printf("[%d:%d] ", i, _tables[i]._kv.first);
				}
				else
				{
					printf("[%d:*] ", i); // 星号代表存储的是无效数据
				}
			}
			cout << endl;
		}
	protected:
		//vector<pair<K, V>> _tables; 为了弄标志位，弄成下一行
		vector<HashData<K, V>> _tables;
		size_t _size = 0; // 存储有效数据的个数
	};
}


namespace HashBucket
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode* _next; // 不用存状态栏了，存下一个结点指针

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template<class K>
	struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放了
	{
		size_t operator()(const K& key)
		{
			return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行
		}
	};

	template<>
	struct HashFunc<string> // 上面的特化
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (const auto& ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		typedef HashNode<K, V> Node;

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		inline size_t __stl_next_prime(size_t n)
		{
			static const size_t __stl_num_primes = 28;
			static const size_t __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return -1; // 不会走到这，顺便返回一个值
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			Hash hs;
			if (_size == _tables.size()) // 负载因子到1就扩容
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newTables;
				//newTables.resize(newSize, nullptr);
				newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数，前两注释改成这一条

				for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hs(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			size_t hashi = hs(kv.first) % _tables.size(); // 哈希映射
			Node* newnode = new Node(kv); // 头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_size;
			return true;
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0) // 防止除零错误
			{
				return false;
			}

			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个
					{
						_tables[hashi] = cur->_next;
					}
					else // 中间删
					{
						prev->_next = cur->_next;
					}
					delete cur; // 统一在这delete
					return true;
				}

				prev = cur; // 往后走
				cur = cur->_next;
			}
			return false; // 没找到
		}

		size_t Size() // 存的数据个数
		{
			return _size;
		}

		size_t TablesSize() // 表的长度
		{
			return _tables.size();
		}

		size_t BucketNum() // 桶的个数
		{
			size_t num = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]) // 如果不是空就有桶
				{
					++num;
				}
			}
			return num;
		}

		size_t MaxBucketLenth() // 最长桶的长度
		{
			size_t maxLen = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				size_t len = 0;
				Node* cur = _tables[i];
				while (cur)
				{
					++len;
					cur = cur->_next;
				}
				if (len > maxLen)
				{
					maxLen = len;
				}
			}
			return maxLen;
		}

	protected:
		vector<Node*> _tables; // 指针数组
		size_t _size;
	};
}